package nc;

/**
 * 题目描述
 *
 *    Redraiment是走梅花桩的高手。Redraiment总是起点不限，从前到后，往高的桩子走，但走的步数最多，不知道为什么？你能替Redraiment研究他最多走的步数吗？
 */

public class Q2312 {

    static Integer[] steps;

    public static int redraiment(int[] heights, int start) {
        // 最多的步数？
        if (steps[start] != null) {
            return steps[start];
        }
        final int height = heights[start];
        int steps =0;
        for (int j = start + 1; j < heights.length; j++) {
            // 寻找比height大的，记录下来
            if (heights[j] > height) {
                // 跳到这里去
                final int l = redraiment(heights, j);
                // 从中找到最大的然后加1返回
                if (l > steps) {
                    steps = l;
                }
            }
        }
        Q2312.steps[start] = steps + 1;
        return steps + 1;
    }

    public static void main(String[] args) {
        final int[] heights = {2, 5, 1, 5, 4, 5};
        steps = new Integer[heights.length];
        int max = 0;
        for (int i = 0;i < heights.length; i ++) {
            // 可以存储下来
            final int redraiment = redraiment(heights, i);
            if (redraiment > max) {
                max = redraiment;
            }
        }
        System.out.println(max);
    }

}
